# 72.编辑距离
# 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
# 你可以对一个单词进行如下三种操作：
# 插入一个字符
# 删除一个字符
# 替换一个字符

def minDistance(word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)

    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

    # 总结 3 种操作：
    # word1 插入一个字符
    # word2 插入一个字符
    # word1 修改一个字符

    # 编辑距离：
    # dp[i][j] word1 的前 i 个字符，到 word2 的前 j 个字符。
    #
    # dp[i-1][j] word1添加一个字符，dp[i][j] = dp[i-1][j] + 1
    # dp[i][j-1] word2添加一个字符，dp[i][j] = dp[i][j-1] + 1
    # dp[i-1][j-1] word1修改一个字符：
    # 判断 word1[i] 和 word2[j] 是否相等？ dp[i][j] = dp[i-1][j-1] + 1 if word1[i] != word2[j] else 0

    # 边界值处理 "" 转 word2
    for column in range(n + 1):
        dp[0][column] = column
    # 边界值处理 word1 转 ""
    for row in range(m + 1):
        dp[row][0] = row

    for i in range(1, m + 1):
        word1_char = word1[i - 1]
        for j in range(1, n + 1):
            word2_char = word2[j - 1]
            # 字符串匹配到
            if word1_char == word2_char:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i - 1][j - 1] - 1, dp[i][j - 1])
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])

    return dp[m][n]


distance = minDistance('intention', 'execution')
print(f"distance:{distance}")

distance = minDistance('xecution', 'execution')
print(f"distance:{distance}")

distance = minDistance('executio', 'execution')
print(f"distance:{distance}")

distance = minDistance('horse', 'ros')
print(f"distance:{distance}")
